// //
// // Created by mac on 2023/11/7.
// //

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    // 1、初始化
    int n = 0, V = 0;
    cin >> n >> V;
    // n 个物品的体积和价值表，其中第 0 个位置仅仅用来占位
    vector<int> v(n + 1), w(n + 1);
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    // 2、建表
    vector< vector<int> > dp(n + 1, vector<int>(V + 1));
    // 解决第一问
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= V; ++j)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);
        }
    cout << dp[n][V] << endl;
    // 解决第二问
    for(int j = 1; j <= V; ++j) dp[0][j] = -1;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= V; ++j)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= v[i] && dp[i][j-v[i]] != -1) dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);
        }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}
/*
- 时间复杂度：O(nV)
- 空间复杂度：O(nV)
*/

// 空间优化版本
//   1. 删除横坐标
//   2. 纵坐标从左往右遍历
int main()
{
    // 1、初始化
    int n = 0, V = 0;
    cin >> n >> V;
    // n 个物品的体积和价值表，其中第 0 个位置仅仅用来占位
    vector<int> v(n + 1), w(n + 1);
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    // 2、建表
    vector<int> dp(V + 1);
    // 解决第一问
    for(int i = 1; i <= n; ++i)
        for(int j = v[i]; j <= V; ++j)
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << dp[V] << endl;
    //解决第二问
    for(int j = 1; j <= V; ++j) dp[j] = -1; // 继续优化：dp[j] = -0x3f3f3f3f
    for(int i = 1; i <= n; ++i)
        for(int j = v[i]; j <= V; ++j)
            // 或者如果用一个非常小的数（例如 -0x3f3f3f3f）代表背包装不满的情况，那么下面的语句就可以不用判断了
            // 直接 dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
            if(dp[j-v[i]] != -1) dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;// 对于上面，修改为 cout << (dp[V] < 0 ? 0 : dp[V]) << endl;

    return 0;
}
/*
- 时间复杂度：O(nV)
- 空间复杂度：O(V)
*/